package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 路径总和III, 可以使用前缀和算法优化
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/9/19
 */
public class Solution437 {
    private int result = 0;

    public int pathSum(TreeNode root, int targetSum) {
        return pathSum(root, targetSum, 0, 0);
    }

    private int pathSum(TreeNode node, long targetSum, long traceSum, int traceLength) {
        if (node == null) {
            return 0;
        }
        int traceNum = 0;
        if (traceSum + node.val == targetSum) {
            traceNum++;
        }
        traceNum += pathSum(node.left, targetSum, traceSum+ node.val, traceLength + 1);
        traceNum += pathSum(node.right, targetSum, traceSum+ node.val, traceLength + 1);
        if (traceLength == 0) {
            traceNum += pathSum(node.left, targetSum, 0, 0);
            traceNum += pathSum(node.right, targetSum, 0, 0);
        }
        return traceNum;
    }

    public static void main(String[] args) {
/*        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        root.right.right = new TreeNode(11);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right.right = new TreeNode(1);*/

        TreeNode root = new TreeNode(1000000000);
        root.left = new TreeNode(1000000000);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        root.right.right = new TreeNode(11);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right.right = new TreeNode(1);

        Solution437 solution = new Solution437();
        System.out.println(solution.pathSum(root, 8));
        int i = 1000000000;
        System.out.println(i);


    }
}